Heap Sort

Max Heap 자료구조를 이용하는 정렬로,
비어있는 Heap에 주어진 수열의 원소를 하나씩 삽입하면^[1], 1차적으로 힙의 특성에 의한 정렬이 이뤄진다. 이를 우선순위 큐에서 꺼내듯이 큰 수부터 차례대로 pop하면, 정렬이 이뤄진다.

힙을 만드는데 드는 시간 $n$과 pop에 필요한 시간 log$n!$을 합한 시간복잡도는
O($n\log n$) 이다.